package com.xjj.homework.w02;

import com.xjj.ListNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class H0023MergeKSortedLists {

    public ListNode mergeKLists(ListNode[] lists) {
        // 分治:假设6组,依次合并要的复杂度是1+2+3+4+5+1*5=20,n^2,两两的话是1*2 + 2*2 + 3*2=12,复杂度应该是nlogn
        // 堆:维护lists.size的最小堆,nlogsize

        /* stackoverflow
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode[] newLists = new ListNode[lists.length / 2 + lists.length % 2];
        for (int i = 0; i < lists.length / 2; i++) {
            newLists[i] = merge(lists[i * 2], lists[i * 2 + 1]);
        }
        if (lists.length % 2 != 0) {
            newLists[newLists.length - 1] = lists[lists.length - 1];
        }
        return mergeKLists(newLists);*/

        Queue<ListNode> queue = new LinkedList<>(Arrays.asList(lists));
        while (queue.size() > 1) {
            queue.add(merge(queue.poll(), queue.poll()));
        }
        return queue.poll();
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        // 哨兵
        ListNode protectNode = new ListNode();
        ListNode last = protectNode;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                last.next = l1;
                l1 = l1.next;
            } else {
                last.next = l2;
                l2 = l2.next;
            }
            last = last.next;
        }
        if (l1 != null) {
            last.next = l1;
        } else {
            last.next = l2;
        }
        return protectNode.next;
    }

}
